\documentclass[a4paper,11pt]{article}
%
% HOW TO USE THIS TEMPLATE:
%
% IN THE TWO INDICATED PLACES BELOW,
%   ENTER YOUR NAMES AND THE NUMBER OF THE HOMEWORK
%
% FOR EACH PROBLEM IN THE SET, WRITE YOUR SOLUTION IN A FILE
%   NAMED "Problem1.tex", "Problem2.tex", etc.
%   THESE SOLUTIONS FILES HAVE NO PREAMBLE AND
%   NO \begin{document} \end{document}
%   (THEY JUST GET INLINED WHEN RUNNING LaTeX)
%
% PLACE THESE SOLUTIONS FILES AND THE TEMPLATE IN THE SAME DIRECTORY
%
% RUN LaTeX
%
% IF YOU NEED TO ADD PACKAGES (E.G., FOR HANDLING FIGURES, OR
%   FOR RUNNING PDFLaTeX), PUT IN A NEW \usepackage LINE AS
%   SHOWN BELOW

%
%%%% REPLACE Doe, Smith, and Wilson WITH YOUR LAST NAMES
%%%% NOTE: IF YOUR LAST NAME HAS ACCENTS, SOME LaTeX COMMANDS ARE:
%%%%       for diaeresis/umlaut ", as in German, use \"a, \"u, \"o, etc.
%%%%       for grave accent `, use \`e, \`a, \`u
%%%%       for acute accent ', use \'a, \'e, \'u
%%%%       for tilde ~, use \tilde{a}, \tilde{o}
%%%%       for caret ^, use \hat{e}, \hat{o}
%%%%	   if you need an accent on an i, say an umlaut, use \"\i{}
%%%%		the \i{} is an i without its dot; e.g., na\"\i{}ve
%%%%	   these all work well with lower-case letters,
%%%%	        but only so-so with upper-case letters
%%%%
  \def\myname{Sintsova, Picorel, and Trigonakis}

%%%% REPLACE xxx WITH CORRECT HOMEWORK NUMBER
%  \def\mynumber{xxx}
  \def\mynumber{8}

  \newcounter{problems}
%%%% REPLACE yyy WITH CORRECT NUMBER OF PROBLEMS IN HOMEWORK
%%%% yyy SHOULD BE A NUMBER BETWEEN 4 AND 7
%  \setcounter{problems}{yyy}
  \setcounter{problems}{5}

%%%% IF ADDITIONAL PACKAGES ARE NEEDED, UNCOMMENT LINE BELOW
%%%% AND ENTER THE PACKAGE NAMES
%  \usepackage{additional_package_1,additional_package_2}



% DO NOT MODIFY THIS NEXT PART
%%%%%
  \usepackage{times,amsmath,pslatex,graphicx,ifthen}
  \newcounter{problem}
  \setcounter{problem}{0}
  \makeatletter
  \def\ps@headings{%
    \let\@mkboth\markboth
    \def\@evenfoot{\hfil\large\sf Homework \mynumber, Problem \theproblem\hfil}
    \def\@oddfoot{\@evenfoot}
    \def\@evenhead{\large\sc\myname\hfil\it\today\hfil\sf P.~\thepage}
    \def\@oddhead{\@evenhead}}
  \makeatother
  \pagestyle{headings}
  \advance\textwidth by16mm
  \advance\oddsidemargin by-8mm
  \advance\textheight by10mm
%%%%%

\usepackage{fancyvrb}
\DefineVerbatimEnvironment{code}{Verbatim}{fontsize=\small}
\DefineVerbatimEnvironment{example}{Verbatim}{fontsize=\small}

\begin{document}

\ifthenelse{\equal{\theproblems}{4}}{%
\begin{center}
  \LARGE\sf
  \begin{tabular}{||c|c|c|c||}
    \hline\hline
    Prob.~1 & Prob.~2 & Prob.~3 & Prob.~4\\
    \hline
    &&&\\
    \hline\hline
  \end{tabular}
\end{center}}{}
\ifthenelse{\equal{\theproblems}{5}}{%
\begin{center}
  \LARGE\sf
  \begin{tabular}{||c|c|c|c|c||}
    \hline\hline
    Prob.~1 & Prob.~2 & Prob.~3 & Prob.~4 & Prob.~5\\
    \hline
    &&&&\\
    \hline\hline
  \end{tabular}
\end{center}}{}
\ifthenelse{\equal{\theproblems}{6}}{%
\begin{center}
  \LARGE\sf
  \begin{tabular}{||c|c|c|c|c|c||}
    \hline\hline
    Prob.~1 & Prob.~2 & Prob.~3 & Prob.~4 & Prob.~5 & Prob.~6\\
    \hline
    &&&&&\\
    \hline\hline
  \end{tabular}
\end{center}}{}
\ifthenelse{\equal{\theproblems}{7}}{%
\begin{center}
  \LARGE\sf
  \begin{tabular}{||c|c|c|c|c|c|c||}
    \hline\hline
    Prob.~1 & Prob.~2 & Prob.~3 & Prob.~4 & Prob.~5 & Prob.~6 & Prob.~7\\
    \hline
    &&&&&&\\
    \hline\hline
  \end{tabular}
\end{center}}{}


\bigskip\bigskip


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{flushleft}
  \addtocounter{problem}{1}
  \large\sf Problem \theproblem .
\end{flushleft}

Recall that Fibonacci numbers are defined by the recurrence $F(n)=F(n-1)+F(n-2)$, with initial conditions $F(0)=0$ and $F(1)=1$. Computing the $nth$ Fibonacci number easily done in $n-1$ addictions. However, we can use divide-and-conquer techniques to compute the $nth$ Fibonacci number with $\Theta(\log n)$ arithmetic operations. Derive such an algorithm.\\

The Fibonacci numbers are defined by the following recurrence:
\begin{flushleft}
$\lbrace F_{n}=F_{n-1}+F_{n-2}$\\
$\lbrace F_{0} = 0 $\\
$\lbrace F_{1} = 1 $\\
\end{flushleft}

Let's transform this recurrence into a linear equation system

\begin{flushleft}
$\lbrace F_{n+1}=F_{n-1}+F_{n}$\\
$\lbrace F_{n}=F_{n}$\\
\end{flushleft}

This is equal to

\begin{flushleft}
$\lbrace F_{n} =0F_{n-1}+1F_{n}$\\
$\lbrace F_{n+1}=1F_{n-1}+1F_{n}$\\
\end{flushleft}

Matrix form

\[
\left( {\begin{array}{c}
 F_{n} \\
 F_{n+1} \\
 \end{array} } \right) 
 =
\left( {\begin{array}{cc}
 0 & 1  \\
 1 & 1  \\
 \end{array} } \right)
 *
 \left( {\begin{array}{c}
 F_{n-1} \\
 F_{n} \\
 \end{array} } \right)
\]

Because we know $F_{0}$ and $F_{1}$

\[
\left( {\begin{array}{c}
 F_{1} \\
 F_{2} \\
 \end{array} } \right) 
 =
\left( {\begin{array}{cc}
 0 & 1  \\
 1 & 1  \\
 \end{array} } \right)
 *
 \left( {\begin{array}{c}
 0 \\
 1 \\
 \end{array} } \right)
\] \\

\[
\left( {\begin{array}{c}
 F_{2} \\
 F_{3} \\
 \end{array} } \right) 
 =
\left( {\begin{array}{cc}
 0 & 1  \\
 1 & 1  \\
 \end{array} } \right)
 *
 \left( {\begin{array}{c}
 F_{1} \\
 F_{2} \\
 \end{array} } \right)
 =
 \left( {\begin{array}{cc}
 0 & 1  \\
 1 & 1  \\
 \end{array} } \right)
 *
 \left( {\begin{array}{cc}
 0 & 1  \\
 1 & 1  \\
 \end{array} } \right)
 *
 \left( {\begin{array}{c}
 0 \\
 1 \\
 \end{array} } \right)
\]

Repeating this over and over

\[
\left( {\begin{array}{c}
 F_{n} \\
 F_{n+1} \\
 \end{array} } \right) 
 =
\left( {\begin{array}{cc}
 0 & 1  \\
 1 & 1  \\
 \end{array} } \right)^n
 *
 \left( {\begin{array}{c}
 0 \\
 1 \\
 \end{array} } \right)
\] \\

Although we need to simplify more this expression. Looking at the matrix of the coefficients

\[
\left( {\begin{array}{cc}
 0 & 1  \\
 1 & 1  \\
 \end{array} } \right)
\]

This expression equals to the first values of the Fibonacci numbers

\[
Q
=
\left( {\begin{array}{cc}
 F_{0} & F_{1}  \\
 F_{1} & F_{2}  \\
 \end{array} } \right)
=
\left( {\begin{array}{cc}
 0 & 1  \\
 1 & 1  \\
 \end{array} } \right)
\]

Let's use the same iteration as in the linear system and multiply by the matrix $A$ to get the subsequent set of Fibonacci numbers:

\[
Q^2
=
\left( {\begin{array}{cc}
 F_{1} & F_{2}  \\
 F_{2} & F_{3}  \\
 \end{array} } \right)
=
\left( {\begin{array}{cc}
 F_{0} & F_{1}  \\
 F_{1} & F_{2}  \\
 \end{array} } \right)
*
\left( {\begin{array}{cc}
 F_{0} & F_{1}  \\
 F_{1} & F_{2}  \\
 \end{array} } \right)
=
\left( {\begin{array}{cc}
 0 & 1  \\
 1 & 1  \\
 \end{array} } \right)^2
 =
 \left( {\begin{array}{cc}
 0 & 1  \\
 1 & 1  \\
 \end{array} } \right)
 *
 \left( {\begin{array}{cc}
 0 & 1  \\
 1 & 1  \\
 \end{array} } \right)
 =
 \left( {\begin{array}{cc}
 1 & 1  \\
 1 & 2  \\
 \end{array} } \right)
\]

Actually this holds. Then, we have the intuition that:

\[
Q^n
=
\left( {\begin{array}{cc}
 F_{n-1} & F_{n}  \\
 F_{n} & F_{n+1}  \\
 \end{array} } \right)
=
\left( {\begin{array}{cc}
 0 & 1  \\
 1 & 1  \\
 \end{array} } \right)^n
\]

Let's prove this by induction

\begin{center}
BASE (n=1)
\end{center}

\[
Q =
\left[ {\begin{array}{cc}
 F_{0} & F_{1}  \\
 F_{1} & F_{2}  \\
\end{array} } \right]
=
\left[ {\begin{array}{cc}
 0 & 1  \\
 1 & 1  \\
\end{array} } \right]
\]\\
$F_{0}=0; F_{1}=1; F_{2}=1;$ This is correct.

\begin{center}
STEP (n+1)
\end{center}

Let's assume that the relation holds for $n$

\[
Q^n =
\left[ {\begin{array}{cc}
 F_{n-1} & F_{n}  \\
 F_{n} & F_{n+1}  \\
\end{array} } \right]
=
\left[ {\begin{array}{cc}
 0 & 1  \\
 1 & 1  \\
\end{array} } \right]^n
\]\\

Let's see for $n+1$

\[
Q^{n+1} =
\left[ {\begin{array}{cc}
 F_{n} & F_{n+1}  \\
 F_{n+1} & F_{n+2}  \\
\end{array} } \right]
=
\left[ {\begin{array}{cc}
 F_{n-1} & F_{n}  \\
 F_{n} & F_{n+1}  \\
\end{array} } \right]
*
\left[ {\begin{array}{cc}
 0 & 1  \\
 1 & 1  \\
\end{array} } \right]
=
\left[ {\begin{array}{cc}
 0 & 1  \\
 1 & 1  \\
\end{array} } \right]^n
*
\left[ {\begin{array}{cc}
 0 & 1  \\
 1 & 1  \\
\end{array} } \right]
=
\left[ {\begin{array}{cc}
 0 & 1  \\
 1 & 1  \\
\end{array} } \right]^{n+1}
\]\\

This also holds for $n+1$ so the equivalence is correct.\\

We know that for calculating the exponential of a number we can use recursive squaring which has a run-time complexity of $\Theta( \log n )$. The recursive squaring algorithm is the following:\\

\begin{flushleft}
$x^{n} \lbrace 1$, $n=1$
\end{flushleft}

\begin{flushleft}
$x^{n} \lbrace (x^{\dfrac{n}{2}})^2$, $n$ is even 
\end{flushleft}

\begin{flushleft}
$x^{n} \lbrace x(x^{\dfrac{(n-1)}{2}})^2$, $n$ is odd 
\end{flushleft}

The final algorithm fill look like this:

\begin{code}
fibonnaci (integer n){

  if (n == 1){
    return Matrix[ 0 1 ; 1 1 ]; O(1)
  }
  
  if (n is even){
    y = fibonacci ( n / 2 ); 
    
    return y * y; -> T(n)=T(n/2)+O(1) 
  }  
  
  if (n is odd){
    y = fibonacci ( (n - 1)/2 )
    
    return y * Matrix[ 0 1 ; 1 1 ]; -> T(n)=T((n-1)/2)+O(1)>= T(n/2)+O(1)
  }
  
}
\end{code}

The algorithm can be expressed like this:

$T(n)=T(n/2)+O(1)$\\

By the Master Theorem we can easily conclude that this algorithm has a run-time complexity of $\Theta(log n)$.

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{flushleft}
  \addtocounter{problem}{1}
  \large\sf Problem \theproblem .
\end{flushleft}

What can you do for the previous problem if some fixed (small) percentage of the people are systematic liars, who lie every single time? (Assume that the percentage of liars is reasonably small.) And is that similar to handling some small percentage of errors in the answers, this time distributed evenly among all answers?.\\

If there a small percentage of liars we can apply the same algorithm as in the previous exercise only this time we should exclude the liars from the list of people. Since we know that there is a small percentage of liars compared to the people truthful we can easy know who is lying. In order to know who is lying we have randomly pick two people $A$ and $B$. We will ask them if they belong to the same party. Then we will ask to the rest of the crowd is $A$ and $B$ belong to the same party. We will make a final count of people who say that [YES] they belong to the same party or [NO] if they say that they don't. The higher counter of the two options will be the response of truthful people. Then, all the people who said the other response will be discarded from the total list of people. Afterwards we just only need to apply the same algorithm used in the exercise $4$.\\

On the other hand, if all the responses have the probability (even small) that the response is not correct we should then probe all the responses because there is a possibility that a majority of the people is not saying the truth. In that case our algorithm developed in the first case won't work in this case.

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\end{document}
